package com.example.programmerinterview;

import java.util.ArrayList;
import java.util.List;

/**
 * 面试题 16.19. 水域大小  类似剑指 Offer 12. 矩阵中的路径 都要使用递归
 * 你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。
 * <p>
 * 示例：
 * <p>
 * 输入：
 * [
 * [0,2,1,0],
 * [0,1,0,1],
 * [1,1,0,1],
 * [0,1,0,1]
 * ]
 * 输出： [1,2,4]
 */
public class PondSizes {
    private static int[][] dic = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
    int m, n;

    public int[] pondSizes(int[][] land) {
        List<Integer> ans = new ArrayList<>();
        m = land.length;
        n = land[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (land[i][j] == 0) {
                    int num = dfs(land, i, j);
                    if (num != 0) {
                        ans.add(num);
                    }
                }
            }
        }
        //list.toArray(T[]) 适用于数组类型相同的，Integer和int不可以互相转化，所以不能用这个函数
        int s = ans.size();
        int[] res = new int[s];
        for (int i = 0; i < s; i++) {
            res[i] = ans.get(i);
        }
        return res;
    }

    private int dfs(int[][] land, int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n || land[x][y] != 0) return 0;
        //小技巧，不用标记数组，用改值来代替
        land[x][y] = -1;
        int num = 1;
        for (int[] a : dic) {
            num += dfs(land, x + a[0], y + a[1]);
        }
        return num;
    }
}
